package com.han.algo_ds.algorithm._24_str_pattern._01brute_force;

import org.junit.Test;

/**
* @author hanpeng
* @version 创建时间：2020年7月25日 下午11:30:53
* @ClassName 类名称
* @Description 类描述 暴力匹配算法解决字符串匹配问题
*/
public class BruteForce {
	public static void main(String[] args) {
		BruteForce bruteForce = new BruteForce();
		System.out.println(bruteForce.pattern3("world", "l"));
	}
	@Test
	public void testPattern() {
		BruteForce bruteForce = new BruteForce();
		System.out.println(bruteForce.pattern("world", "or"));

	}
	/**
	 * @param text 文本串
	 * @param pattern 模式串
	 * @return -1 不匹配  >=0 匹配索引位置
	 */
	public int pattern(String text,String pattern) {
		checkNotNull(text);
		checkNotNull(pattern);
		char[] textArr = text.toCharArray();
		char[] patternArr= pattern.toCharArray();
		int tl = textArr.length;
		int pl = patternArr.length;        
		for (int i = 0; i < tl; i++) {
			for (int k = 0; k < pl; k++) {
				if (textArr.length - i >= patternArr.length) {
					char pc = patternArr[k];
					char tc = textArr[k + i];
					if (k == pl-1 && pc == tc) {
						return i;
					}
					if (pc != tc) {
						break;
					}
				}
			}
		}
		return -1;
	}
	public int pattern2(String text,String pattern) {
		if(text==null||pattern==null) {return -1;}
		char[] textChars = text.toCharArray();
		
		int tLen = textChars.length;
		if(tLen==0) {return -1;}
		
		char[] patternChars = pattern.toCharArray();
		int pLen = patternChars.length;
		if(pLen==0) {return -1;}
		if (tLen<pLen) {
			return -1;
		}
		int ti=0;
		int pi=0;
		while (pi<pLen&&ti<tLen) {
			if(textChars[ti]==patternChars[pi]) {
				ti++;
				pi++;
			} else {
				//ti 回溯  
				//
				ti=ti-(pi-1);
				pi=0;
			}
		}
		
		return (pi==pLen)?(ti-pi):-1;
	}
	//pattern2优化
	public int pattern3(String text,String pattern) {
		if(text==null||pattern==null) {return -1;}
		char[] textChars = text.toCharArray();
		
		int tLen = textChars.length;
		if(tLen==0) {return -1;}
		
		char[] patternChars = pattern.toCharArray();
		int pLen = patternChars.length;
		if(pLen==0) {return -1;}
		if (tLen<pLen) {
			return -1;
		}
		int ti=0;
		int pi=0;
		int deltaLen=tLen-pLen;
		//w o r l d
		//      l d
		//比较的最大索引值为 tLen-pLen
		//ti 应该是回溯比较 ti-pi  ti-pi是一轮比较中文本串首个字符的位置
		while (pi<pLen&&ti-pi<=deltaLen) {
			if(textChars[ti]==patternChars[pi]) {
				ti++;
				pi++;
			} else {
				//ti 回溯  
				//
				ti=ti-(pi-1);
				pi=0;
			}
		}
		
		return (pi==pLen)?(ti-pi):-1;
	}
	public void checkNotNull(String str) {
		if(str==null) {
			throw new IllegalArgumentException("字符串不能为空");
		}
	}
}
